nums=[9,28,50,9,34,48,2,50,38,10,5,16,44,5,48,21,38,17,21,49]
target = 20
#dfs深度优先遍历
def dfs(nums,target,sumCur,depth,res):
    #出口条件
    if depth>=len(nums):
        if sumCur==target:
            return 1
        return 0
    left=dfs(nums,target,sumCur-nums[depth],depth+1,res)
    right=dfs(nums,target,sumCur+nums[depth],depth+1,res)
    return left+right
def findTargetSumWays(nums,target):
    res=[0]
    return dfs(nums,target,0,0,res)


print(findTargetSumWays(nums,target))

def findTargetSumWays1(nums,target):
    numsLenght=len(nums)
    #状态转移矩阵
    dp=[[0 for _ in range(2001)] for _ in range(numsLenght)]
    #先处理第一行
    dp[0][1000-nums[0]]=1
    dp[0][1000+nums[0]]=1
    #处理剩余行数
    for i in range(1,numsLenght):
        for j in range(1000-target,1000+target):
            if j-nums[i]>=0 and j+nums[i]<2*1000+1:
                dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]
        # print(dp[0][1000-target:1000+target+1])
        print(dp[i][1000-target-5:1000+target+5])

        print(dp[numsLenght-1][1000+target])
# findTargetSumWays1(nums,target)